package com.shuo.dsa.niuke;

import com.shuo.dsa.model.RandomListNode;

/**
 * 复杂链表的复制
 *      思路: 先遍历一遍, new出个新节点接后面, 最后遍历拆分链+填随机
 */
public class CopyListRandom {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode cur = head;
        while (cur != null) {
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.next = cur.next;
            newNode.random = cur.random;
            RandomListNode next = cur.next;
            cur.next = newNode;
            cur = next;
        }
        cur = head;
        while (cur != null) {
            RandomListNode newNode = cur.next;
            newNode.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        RandomListNode ret = cur.next;
        while (cur != null) {
            RandomListNode newNode = cur.next;
            cur.next = newNode.next;
            newNode.next = newNode.next == null ? null : newNode.next.next;
            cur = cur.next;
        }
        return ret;
    }
}
